#include "skiplist.h"
#include <string.h>
#include <stdlib.h>
static int zslRandomLevel()
{
    //test
    return random() % ZSKIPLIST_MAXLEVEL;
}
zskiplistNode *zslCreateNode(int level, double score, sds ele)
{
    zskiplistNode *zn = malloc(sizeof(*zn) + level * sizeof(struct zskiplistLevel));
    zn->ele = ele;
    zn->score = score;
    return zn;
}

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele)
{
    //update数组，记录新插入节点每一层的前一个节点
    //x为当前所处的节点
    //rank到header的距离
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    x = zsl->header;
    for (i = zsl->level - 1; i >= 0; i++)
    {
        rank[i] = i == (zsl->level - 1) ? 0 : rank[i + 1];
        //我们从最高级开始比较，如果是最高层，那么意味着我们以header为基础，rank[i] = 0

        //从该层的第一个节点开始往后比较，直到后面没有节点或者节点的score>=待插入的节点的score
        while (x->level[i].forward &&
               (x->level[i].forward->score < score ||
                strcmp(x->level[i].forward->ele, ele) < 0))
        {
            rank[i] = x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }

    level = zslRandomLevel();
    if (level > zsl->level)
    {
        for (i = zsl->level; i < level; i++)
        {
            //对于新增的level，其前一节点定为header
            rank[i] = 0;
            update[i] = zsl->header;

            //将前一节点的span指定为length，以便后面更新跳跃表中的数据
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    x = zslCreateNode(level, score, ele);
    for (i = 0; i < level; i++)
    {
        //更新链表
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;

        //更新两边的span
        //rank[0] - rank[i]为新插入节点到前一节点的距离
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    //比此次的level还要高的节点span++
    for (i = level; i < zsl->level; i++)
    {
        update[i]->level[i].span++;
    }

    //更新backward
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0]->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
}